package LeetCode;

import java.util.Arrays;
import java.util.Comparator;

public class LC_435_NonoverlappingIntervals {

    public static void main(String[] args) {

    }


    public class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    public class Solution {
        boolean isOverlapping(Interval i, Interval j) {
            return i.end > j.start;
        }

        public int eraseOverlapIntervals(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) return 0;
            Arrays.sort(intervals, Comparator.comparingInt(a -> a.start));
            int dp[] = new int[intervals.length];
            dp[0] = 1;
            int ans = 1;
            for (int i = 1; i < dp.length; i++) {
                int max = 0;
                for (int j = i - 1; j >= 0; j--)
                    if (!isOverlapping(intervals[j], intervals[i])) max = Math.max(dp[j], max);
                dp[i] = max + 1;
                ans = Math.max(ans, dp[i]);
            }
            return intervals.length - ans;
        }

    }
}
